package com.example.leetcode.c1_c100.c19;
/**
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 *
 * 示例：
 *
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 *
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 * 说明：
 *
 * 给定的 n 保证是有效的。
 *
 * 进阶：
 *
 * 你能尝试使用一趟扫描实现吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


import com.example.leetcode.common.ListNode;
import com.example.leetcode.common.ListOperate;

/**
 * 删除链表的倒数第N个节点
 * @author zhanpengguo
 * @date 2020-09-09 12:21
 */
public class Solution {

    public static void main(String[] args) {
        ListNode listNode = ListOperate.create(new int[]{1,2,3,4,5});
        Solution solution = new Solution();
        ListNode listNode1 = solution.removeNthFromEnd(listNode, 1);
        while (listNode1 != null) {
            System.out.println(listNode1.val);
            listNode1 = listNode1.next;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n == 0) {
            return head;
        }
        // 双指针
        ListNode temp = head;
        // 第n个节点
        for (int i = 0; i < n; i++) {
            temp = temp.next;
        }
        if (temp == null) {
            return head.next;
        }
        ListNode res = head;
        while (head != null) {
            if (temp.next == null) {
                head.next = head.next.next;
                break;
            }
            temp = temp.next;
            head = head.next;
        }
        return res;
    }
}
